Introduction to the Search Service

Introduction #

These days, most websites and applications provide search functionalities due to a number of advantages the search feature brings. For example, GitHub uses the search API to efficiently find a specific file or repository from more than 200 million repositories.

The search API takes a search query from a user and searches for relevant records based on the parameters in the query, as depicted in the following figure. In return, the user may get varied responses, including images, thumbnails of videos, recommendations, sponsored or featured advertisements, and primarily text results.

The search API can perform multiple operations on the matched records, such as limiting or sorting the number of records to return. In order to design the API for the search service, it’s important to understand the internal workings of the service. This background knowledge will help us optimally design different aspects of the API, such as communication protocols between the client and the server, middleware, and back-end services.

Let's discuss how the search service performs different functionalities.

How does the search service work?#

To understand how the search system works, let's take a look at the following illustration that consists of an indexer and searcher.

When the search service receives a query, it is forwarded to the searcher. The searcher parses the query and looks into the index table to find the matching results. The index table consists of the terms and their mappings, which are created by the indexer. The responsibility of the indexer is to pre-index data as soon as it’s posted so that the searcher can quickly respond to search queries. The searcher aggregates all the results corresponding to the query and returns them to the search service. The following table describes the responsibilities of each component in the search service.

In response to a search query, the number of records can vary from zero to hundreds of thousands. Because of this, the data payload and time taken could be very large. Consequently, a limiting factor on the number of records to present to the user is required. This avoids overwhelming the client and burdening the back-end servers. For this purpose, we’ll use the pagination technique, which is discussed in the following sections.

Note: To read more on the internal workings of a search service, please visit our Design of a Distributed Search lesson in the Grokking Modern System Design Interview for Engineers & Managers course.

Ordinarily, some queries are long or computationally heavy. Here, we assume our service focuses more on delivering quick and relevant results than exact matches. Therefore, we set a maximum time limit for long and complex queries to provide a fast API response. If the time limit is exceeded for a complex query, which is a rare case, the API might return a partial response. Similarly, we limit the length of a user query to be accepted by our API. For example, the query should not be longer than 200 characters.

Let's explore some interesting functionalities of the search service.

Sorting#

One of the core features of the search service includes the sorting of the searched results. Sorting can be performed based on a parameter or group of parameters.

A typical search query that includes sorting is given below:

The search query above returns a list of transactions sorted from the most recent to the oldest. A query without the sort parameter returns records in either ascending or descending order, depending on the default configuration. We have set ascending as the default order for the search API.

Sorting can be applied to multiple parameters whenever needed. For example, the following query sorts the date and the name parameters in descending and ascending order, respectively. One advantage of sorting is to allow users to find the most recent or oldest data quickly.

The next concern is that the response returned by the API might contain a long list of results. If we transmit all these results in a single response over the network, the latency will increase and consume more bandwidth. Also, client applications will have to perform intensive tasks, such as rendering while displaying these results. Especially with mobile devices, it may waste more energy to display large amounts of data that the user may not even see, and we also want to save battery. So, the API should be flexible enough to divide the matched data into different sets via a feature known as pagination, as discussed in the following section.

Pagination#

Pagination is a technique that divides an immense amount of data into pages, batches, or chunks. It helps to limit the number of records in the response, minimize the payload, improve API response time, and reduce traffic over the network. Responding with hundreds of results is useless because most users limit their search to the top 10 results only. Pagination helps in reducing the burden on both ends.

Note: The same response for a different type of client may not be the optimal solution because different clients (such as devices with different screen sizes, like mobile, laptop, and so on) may require variations in the items per page. Therefore, we need to send the page number and number of items per page to the server based on the client type or the user's use cases. Apart from that, the server can autogenerate pagination parameters by identifying the type of client to give a flexible response.

Let's discuss different approaches that will help us paginate our API response results.

Skip limit pagination#

Designing an API with the skip and limit parameters is an easy way to implement pagination. The skip parameter indicates the number of records that should be skipped before returning the intended records, and the limit parameter indicates the maximum number of results to return against one request. The names of these parameters depend on the server-side implementation. Some service providers call it start and end instead of skip and limit.

An example of how the service gets the first 10 (0–9) results using the two parameters is given below:

The client sends another request to get search results in the range of 10–19 via the following URL:

If the size of the search results is less than 10, the API will return them as they are.

Cursor pagination#

Each time a new page request is sent, skip and limit pagination must skip the results from the beginning and return the expected records. Cursor pagination is performed on sequential columns (such as timestamp, id, and so forth) of the database. It uses the last retrieved search result as a pointer to fetch the next page of records. This allows cursor pagination to fetch results by performing a direct query based on the next page pointer rather than skipping results from the beginning for each subsequent request, similar to skip and limit pagination.

Let’s assume that the client calls the /search?query=course&limit=15 endpoint. The result obtained from this call will contain 15 records and a pointer called next-cursor, as shown in the code below. The next-cursor acts as a pointer to the next 15 results.

Cursor pagination works similarly to skip and limit pagination, i.e., the client application maintains a specific value to indicate where to start returning the next chunk. However, in skip and limit pagination, the skip value is the number of pages to skip, while in cursor pagination, the next-cursor is the value of a field from a record that can be used to compare and fetch records sequentially. The pointer, next-cursor, is used in the subsequent requests by passing it in the URL to fetch the next results in the following way:

As seen above, the next-cursor defines a pointer to the next page but does not specify a way to move directly to a random page. Therefore, this technique is good for implementing the frontend that facilitates scrolling and automatically sends a request for the next set of search results to be displayed on the same web page. For use cases where users are expected to jump randomly between different pages, this approach may not be suitable to use.

Another pattern that allows us to perform pagination efficiently is the bucket pattern. Let's discuss how it overcomes the sequential access limitation of cursor pagination.

Bucket pattern#

The bucket pattern divides search results into groups of fixed size. These groups are also called buckets. However, each bucket is skipped using a pattern similar to skip and limit pagination. The difference here is that it improves efficiency by skipping buckets instead of skipping records one by one.

The bucket pattern merges multiple results associated with the same query into single or multiple documents depending on the total count of search results. Take a look at the search results for the query "data structure." The associated document for this query will be generated like the one on the right side.

Let's see an example. We’ll assume we have 5,000 search results against a query, and the user wants to go to page 15. Our back-end system defines the bucket size to 10 and paginates 5,000 results into 500 buckets. The API skips 14 buckets to get results for page 15. The client sends the following request to go to page 15:

Here the skip parameter is used to skip the first 14 buckets.

The following table assists us in choosing which technique to opt for in specific use cases.

In this lesson, we got an idea of how the search service works and the associated pagination techniques to retrieve results efficiently based on a user query. We’ll use this information as a foundation to draw up the workflow of a search API and its associated services.